package com.ocean.heap;

/**
 * 堆是一个完全二叉树；
 * 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/13 <br>
 */
public class Heap {
    private int count; // 元素的数量
    private int[] a; // 用数组存放元素 从下标1开始
    private int n; // 堆可存放的元素数量

    public Heap(int capacity) {
        this.a = new int[capacity + 1];
        this.n = capacity;
        this.count = 1;
    }

    public void insert(int ele) {
        // 判断堆是否满
        if (count >= n) {
            return;
        }
        ++count;
        a[count] = ele;
        // 上堆化处理
        int i = count;
        while (i / 2 > 0 && a[i] > a[i / 2]) {
            // 交换
            swap(this.a, i, i / 2);
            i = i / 2;
        }
    }


    public void removeMax() {
        if (count == 0) {
            return;
        }
        a[1] = a[count];
        --count;
        heapify(a, count, 1);
    }


    private void buildHeap(int[] a, int n) {
        for (int i = n / 2; i >= 1; --i) {
            heapify2(a, n, i);
        }
    }

    private void heapify2(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && a[i] < a[i * 2]) {
                maxPos = i * 2;
            }
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            if (maxPos == i) {
                break;
            }
            swap(a, i, maxPos);
            i = maxPos;
        }
    }


    private void heapify(int[] a, int n, int i) { // 自上往下堆化
        while (true) {
            int maxPos = i;
            if (i * 2 <= n && a[i] < a[i * 2]) {
                maxPos = i * 2;
            }
            if (i * 2 + 1 <= n && a[maxPos] < a[i * 2 + 1]) {
                maxPos = i * 2 + 1;
            }
            if (maxPos == i) {
                break;
            }
            swap(a, i, maxPos);
            i = maxPos;
        }
    }


    private void swap(int[] a, int curIndex, int parentIndex) {
        int temp = a[curIndex];
        a[curIndex] = a[parentIndex];
        a[parentIndex] = temp;
    }
}
